package 笔试记录.M10day21百度实习;

public class main1 {

    public static void main(String[] args) {
        int[] arr = {1,3,6,8,3,6,10};
        quickSort(arr,0,arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void quickSort(int[] arr,int left,int right){
        if(right - left > 1){
            int index = partion(arr,left,right);
            quickSort(arr,left,index);
            quickSort(arr,index + 1,right);
        }
    }

    public static int partion(int[] arr,int left,int right){
        int index = right - 1;//可以取到
        int key = arr[index];
        int begin = left;
        int end = index;
        while(begin < end){
            while(begin < end && arr[begin] <= key) begin++;
            while(begin < end && arr[end] >= key) end--;

            if(begin < end) swap(arr,begin,end);
        }

        swap(arr,begin,right - 1);
        return begin;
    }

    public static void swap(int[] arr,int left,int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
}
